package com.yiguang.algorithm.dp;


public class KnightDialer {

	private char[][] phone = {{1,2,3},{4,5,6},{7,8,9},{'*',0,'#'}};
	
	private int rowLen = phone.length;
	
	private int colLen = phone[0].length;
	
	private int result;
	
	public int getDifferentCount(int n) {
		int result = 0;
		for(int i=0; i<phone.length; i++) {
			for(int j=0; j<phone[0].length; j++) {
				if((i==3&&j==0) || (i==3&&j==2)) {
					continue;
				}
				result += dfs(i,j,1,n,0);
				//System.out.println(result);
				//System.out.println("------------------");
			}
		}
		return result;
	}
	
	public int dfs(int row, int column, int num, int n, int result) {
		if(num==n) {
			++result;
			return result;
		}
		
		// top
		if(row-2>=0&&column-1>=0&&phone[row-2][column-1]!='*'&&phone[row-2][column-1]!='#') {
			result=dfs(row-2,column-1,num+1,n,result);
		}
		if(row-2>=0&&column+1<colLen&&phone[row-2][column+1]!='*'&&phone[row-2][column+1]!='#') {
			result=dfs(row-2,column+1,num+1,n,result);
		}
		// right
		if(column+2<colLen&&row-1>=0&&phone[row-1][column+2]!='*'&&phone[row-1][column+2]!='#') {
			result=dfs(row-1,column+2,num+1,n,result);
		}
		if(column+2<colLen&&row+1<rowLen&&phone[row+1][column+2]!='*'&&phone[row+1][column+2]!='#') {
			result=dfs(row-1,column+2,num+1,n,result);
		}
		// bottom
		if(row+2<rowLen&&column+1<colLen&&phone[row+2][column+1]!='*'&&phone[row+2][column+1]!='#') {
			result=dfs(row+2,column+1,num+1,n,result);
			//System.out.println(result);
		}
		if(row+2<rowLen&&column-1>=0&&phone[row+2][column-1]!='*'&&phone[row+2][column-1]!='#') {
			result=dfs(row+2,column+1,num+1,n,result);
			//System.out.println(result);
		}
		// left
		if(column-2>=0&&row+1<rowLen&&phone[row+1][column-2]!='*'&&phone[row+1][column-2]!='#') {
			result=dfs(row+1,column-2,num+1,n,result);
			//System.out.println(result);
		}
		if(column-2>=0&&row-1>=0&&phone[row-1][column-2]!='*'&&phone[row-1][column-2]!='#') {
			result=dfs(row-1,column-2,num+1,n,result);
			//System.out.println(result);
		}
		return result;
	}
	
	private static final int MOD = 1_000_000_007;
    public int knightDialer(int n) {
        long[] dp = new long[10];
        long[] temp = new long[10];
        for (int i = 0; i < 10; i++) {
            dp[i] = 1;
        }

        for (int i = 1; i < n; i++) {
            temp[0] = (dp[4] + dp[6]) % MOD;
            temp[1] = (dp[6] + dp[8]) % MOD;
            temp[2] = (dp[7] + dp[9]) % MOD;
            temp[3] = (dp[4] + dp[8]) % MOD;
            temp[4] = (dp[0] + dp[3] + dp[9]) % MOD;
            temp[5] = 0;
            temp[6] = (dp[0] + dp[1] + dp[7]) % MOD;
            temp[7] = (dp[2] + dp[6]) % MOD;
            temp[8] = (dp[1] + dp[3]) % MOD;
            temp[9] = (dp[2] + dp[4]) % MOD;
            for (int j = 0; j < 10; j++) {
                dp[j] = temp[j];
            }
        }

        long res = 0;
        for (int i = 0; i < 10; i++) {
            res = (res + dp[i]) % MOD;
        }
        return (int) res;
    }
    
    /*
     * 1349. 参加考试的最大学生数
     * 状态dp
     */
    public int maxStudents(char[][] seats) {
    	
    	return 1;
    }
	
	public static void main(String[] args) {
		KnightDialer knightDialer = new KnightDialer();
		int result1 = knightDialer.getDifferentCount(4);
		int result2 = knightDialer.knightDialer(4);
		System.out.println(result1);
		System.out.println(result2);
	}
}
